زبان امگا

به هر مجموعه از رشته‌های به طول نامتناهی از یک الفبای مشخص، یک زبان امگا (زبان ω) تعریف شده بر روی آن الفبا می‌گویند.

تعریف رسمی

فرض می‌کنیم Σ الفبایی دلخواه باشد. یک رشته نامتناهی، که به آن رشته امگا نیز گفته می‌شود، یک توالی نامتناهی از حروف الفبای Σ به صورت ${\ce {a0a1a2...}}$ است. همان‌طور که هر رشته متناهی به طول n از الفبای Σ را می‌توان با یک تابع به صورت $f:\{0,1,2,...,n-1\}\rightarrow \Sigma$ نمایش داد که در آن $f(i)$ نمایش حرف i ام رشته‌است، هر رشته امگا از این الفبا را نیز می‌توان به صورت یک تابع $f:N\rightarrow \Sigma$ در نظر گرفت که در آن $f(n)$ حرف n ام در رشته مورد نظر است. هم چنین در مقابل $\Sigma ^{*}$ که در نظریه زبان صوری به مجموعه همه رشته‌های متناهی از الفبای Σ گفته می‌شود، مجموعه همهٔ رشته‌های امگا که بر روی الفبای Σ تعریف می‌شود با $\Sigma ^{\omega }$ نشان داده می‌شود. اجتماع $\Sigma ^{\omega }$ و $\Sigma ^{*}$ یعنی مجموعه همهٔ رشته‌های الفبای Σ با $\Sigma ^{\infty }$ نمایش داده می‌شود.

به هر مجموعه $L\subseteq \Sigma ^{\omega }$ از رشته‌های امگا، یک زبان امگا گفته می‌شود.

کاربرد

تأیید برنامه (verification): به عنوان کدبندی اجراهای پایان‌ناپذیر یک برنامه.

حساب (arithmetic): به عنوان کدبندی‌های مجموعه‌های اعداد حقیقی.

تکرار ω (تکرار بی‌نهایت)

تکرار ω (به انگلیسی: ω-iteration) برای زبان $L\subseteq \Sigma ^{*}$، زبان امگای $L^{\omega }$ است که به صورت $L^{\omega }=\{w_{1}w_{2}w_{3}...|\ w_{i}\in L\setminus \{\epsilon \}\}$ تعریف می‌شود.

توجه داریم که برخلاف مفهوم مشابه در مورد رشته‌های متناهی که در آن $\{\epsilon \}^{*}=\{\emptyset \}$، در مورد تکرار ω تساوی $\{\epsilon \}^{\omega }=\{\emptyset \}$ به این دلیل که همهٔ رشته‌های $L^{\omega }$ باید دارای طول نامتناهی باشند، نمی‌تواند درست باشد و بنابراین داریم: $\{\epsilon \}^{\omega }=\emptyset$.

عملیات‌های زبان امگا

برخی از عملیات‌های تعریف شده بر روی زبان‌های امگا عبارت‌اند از:

• اجتماع و اشتراک: اگر $L$ و $L^{'}$ دو زبان امگا باشند، اجتماع و اشتراک آنها نیز زبان امگا هستند که به ترتیب به صورت $L\cup L^{'}=\{w\ |\ w\in L\ \lor w\in L^{'}\}$ و $L\cap L^{'}=\{w\ |\ w\in L\ \land w\in L^{'}\}$ تعریف می‌شوند.
• الحاق: الحاق یک زبان امگای $L$ و یک زبان یا زبان امگای $L^{'}$، یک زبان امگا است که به صورت $L.L^{'}=\{w_{1}w_{2}\ |\ w_{1}\in L\ \land w_{2}\in L^{'}\}$ تعریف می‌شود.
• پیشوند: اگر w یک رشته امگا باشد، زبان صوری $pref(w)$ همهٔ پیشوندهای w را در خود دارد و پیشوند w نامیده می‌شود.
• حد: اگر $L$یک زبان با طول متناهی باشد، رشته امگای w را در حد $L$ می‌گوییم اگر و تنها اگر $pref(w)\cap L$ یک مجموعه نامتناهی باشد. عملیات حد بر روی زبان $L$ را با $L^{\delta }$ نشان می‌دهیم.

فاصله بین رشته‌های امگا

فاصله بین دو رشته امگا به صورت یک تابع به شکل $d:\Sigma ^{\omega }\times \Sigma ^{\omega }\rightarrow R$ تعریف می‌شود که در آن $d(w_{1},w_{2})=inf\{2^{-|x|}:x\in \Sigma ^{*}\ \land \ x\in pref(w_{1})\ \land \ x\in pref(w_{2})\}$.

در تعریف بالا $|x|$ طول x و inf زیرینه در مجموعه اعداد حقیقی است.

به این ترتیب اگر $w_{1}=w_{2}$ خواهیم داشت: $d(w_{1},w_{2})=0$.

زیرکلاس‌ها

مهمترین زیر کلاس زبان‌های امگا، زبان‌های منظم امگا (به انگلیسی: omega-regular) هستند که تعریف زبان‌های منظم را به رشته‌های نامتناهی تعمیم می‌دهند.

Julius Richard Büchi

زبان‌های منظم امگا

زبان امگای L یک زبان منظم امگا است اگر به یکی از شکل‌های زیر باشد:

• $A^{\omega }$ که در آن A یک زبان منظم غیر تهی است که رشته تهی را در خود ندارد.
• $A.B$ که در آن A یک زبان منظم و B یک زبان منظم امگا است.
• $A\cup B$ که در آن A و B زبان‌های منظم امگا هستند.

ماشین Büchi

ماشین Büchi که توسط J.R. Büchi تعریف شده‌است به عنوان تشخیص دهنده زبان‌های منظم امگا مطرح می‌باشد که به این ترتیب مسئله عضویت این زبان‌ها تصمیم‌پذیر با وجود این ماشین تصمیم پذیر خواهد بود.

مثالی از ماشین Büchi

شکل ظاهری این ماشین مانند DFA و NFA است اما شرط پذیرش در آن متفاوت است.

منابع

• Vincent Carnino, Sylvain Lombardy. Factorizations and Universal Automaton of Omega Languages. Developments in Language Theory, 2013
• Handbook of Formal Languages: Volume 3 Beyond Words
• Marcelo d’Amorim , Grigore Ro¸su. Efficient Monitoring of ω-Languages
• Dana Angluin, Dana Fisman. Learning Regular Omega Languages
• Omega-automaton